#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode() 
        : val(0), left(nullptr), right(nullptr) 
    {}
    TreeNode(int x) 
        : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (!preorder.size()) {
        return nullptr;
    }
    TreeNode* root = new TreeNode(preorder[0]);
    stack<TreeNode*> stk;
    stk.push(root);
    int inorderIndex = 0;
    for (int i = 1; i < preorder.size(); ++i) {
        int preorderVal = preorder[i];
        TreeNode* node = stk.top();
        if (node->val != inorder[inorderIndex]) {
            node->left = new TreeNode(preorderVal);
            stk.push(node->left);
        }
        else {
            while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) {
                node = stk.top();
                stk.pop();
                ++inorderIndex;
            }
            node->right = new TreeNode(preorderVal);
            stk.push(node->right);
        }
    }
    return root;
}

void preorder(TreeNode* root)
{
    if (root == nullptr)
        return;

    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

void inorder(TreeNode* root)
{
    if (root == nullptr)
        return;

    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main()
{
    vector<int> pre = { 3,9,4,5,20,15,7 };
    vector<int> in = { 4,9,5,3,15,20,7 };

    //vector<int> pre = { 3,9,20,15,7 };
    //vector<int> in = { 9,3,15,20,7 };

    TreeNode* root = buildTree(pre, in);
    preorder(root);
    cout << endl;
    inorder(root);

    return 0;
}

